home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / xfs / xfs_attr_leaf.h < prev    next >
C/C++ Source or Header  |  2005-10-18  |  13KB  |  310 lines
  1. /*
  2.  * Copyright (c) 2000, 2002-2003 Silicon Graphics, Inc.  All Rights Reserved.
  3.  *
  4.  * This program is free software; you can redistribute it and/or modify it
  5.  * under the terms of version 2 of the GNU General Public License as
  6.  * published by the Free Software Foundation.
  7.  *
  8.  * This program is distributed in the hope that it would be useful, but
  9.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  *
  12.  * Further, this software is distributed without any warranty that it is
  13.  * free of the rightful claim of any third person regarding infringement
  14.  * or the like.  Any license provided herein, whether implied or
  15.  * otherwise, applies only to this software file.  Patent licenses, if
  16.  * any, provided herein do not apply to combinations of this program with
  17.  * other software, or any other product whatsoever.
  18.  *
  19.  * You should have received a copy of the GNU General Public License along
  20.  * with this program; if not, write the Free Software Foundation, Inc., 59
  21.  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22.  *
  23.  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24.  * Mountain View, CA  94043, or:
  25.  *
  26.  * http://www.sgi.com
  27.  *
  28.  * For further information regarding this notice, see:
  29.  *
  30.  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31.  */
  32. #ifndef __XFS_ATTR_LEAF_H__
  33. #define    __XFS_ATTR_LEAF_H__
  34.  
  35. /*
  36.  * Attribute storage layout, internal structure, access macros, etc.
  37.  *
  38.  * Attribute lists are structured around Btrees where all the data
  39.  * elements are in the leaf nodes.  Attribute names are hashed into an int,
  40.  * then that int is used as the index into the Btree.  Since the hashval
  41.  * of an attribute name may not be unique, we may have duplicate keys.  The
  42.  * internal links in the Btree are logical block offsets into the file.
  43.  */
  44.  
  45. struct attrlist;
  46. struct attrlist_cursor_kern;
  47. struct attrnames;
  48. struct xfs_dabuf;
  49. struct xfs_da_args;
  50. struct xfs_da_state;
  51. struct xfs_da_state_blk;
  52. struct xfs_inode;
  53. struct xfs_trans;
  54.  
  55. /*========================================================================
  56.  * Attribute structure when equal to XFS_LBSIZE(mp) bytes.
  57.  *========================================================================*/
  58.  
  59. /*
  60.  * This is the structure of the leaf nodes in the Btree.
  61.  *
  62.  * Struct leaf_entry's are packed from the top.  Name/values grow from the
  63.  * bottom but are not packed.  The freemap contains run-length-encoded entries
  64.  * for the free bytes after the leaf_entry's, but only the N largest such,
  65.  * smaller runs are dropped.  When the freemap doesn't show enough space
  66.  * for an allocation, we compact the name/value area and try again.  If we
  67.  * still don't have enough space, then we have to split the block.  The
  68.  * name/value structs (both local and remote versions) must be 32bit aligned.
  69.  *
  70.  * Since we have duplicate hash keys, for each key that matches, compare
  71.  * the actual name string.  The root and intermediate node search always
  72.  * takes the first-in-the-block key match found, so we should only have
  73.  * to work "forw"ard.  If none matches, continue with the "forw"ard leaf
  74.  * nodes until the hash key changes or the attribute name is found.
  75.  *
  76.  * We store the fact that an attribute is a ROOT/USER/SECURE attribute in
  77.  * the leaf_entry.  The namespaces are independent only because we also look
  78.  * at the namespace bit when we are looking for a matching attribute name.
  79.  *
  80.  * We also store a "incomplete" bit in the leaf_entry.  It shows that an
  81.  * attribute is in the middle of being created and should not be shown to
  82.  * the user if we crash during the time that the bit is set.  We clear the
  83.  * bit when we have finished setting up the attribute.  We do this because
  84.  * we cannot create some large attributes inside a single transaction, and we
  85.  * need some indication that we weren't finished if we crash in the middle.
  86.  */
  87. #define XFS_ATTR_LEAF_MAPSIZE    3    /* how many freespace slots */
  88.  
  89. typedef struct xfs_attr_leafblock {
  90.     struct xfs_attr_leaf_hdr {    /* constant-structure header block */
  91.         xfs_da_blkinfo_t info;    /* block type, links, etc. */
  92.         __uint16_t count;    /* count of active leaf_entry's */
  93.         __uint16_t usedbytes;    /* num bytes of names/values stored */
  94.         __uint16_t firstused;    /* first used byte in name area */
  95.         __uint8_t  holes;    /* != 0 if blk needs compaction */
  96.         __uint8_t  pad1;
  97.         struct xfs_attr_leaf_map {      /* RLE map of free bytes */
  98.             __uint16_t base;      /* base of free region */
  99.             __uint16_t size;      /* length of free region */
  100.         } freemap[XFS_ATTR_LEAF_MAPSIZE]; /* N largest free regions */
  101.     } hdr;
  102.     struct xfs_attr_leaf_entry {    /* sorted on key, not name */
  103.         xfs_dahash_t hashval;    /* hash value of name */
  104.         __uint16_t nameidx;    /* index into buffer of name/value */
  105.         __uint8_t flags;    /* LOCAL/ROOT/SECURE/INCOMPLETE flag */
  106.         __uint8_t pad2;        /* unused pad byte */
  107.     } entries[1];            /* variable sized array */
  108.     struct xfs_attr_leaf_name_local {
  109.         __uint16_t valuelen;    /* number of bytes in value */
  110.         __uint8_t namelen;    /* length of name bytes */
  111.         __uint8_t nameval[1];    /* name/value bytes */
  112.     } namelist;            /* grows from bottom of buf */
  113.     struct xfs_attr_leaf_name_remote {
  114.         xfs_dablk_t valueblk;    /* block number of value bytes */
  115.         __uint32_t valuelen;    /* number of bytes in value */
  116.         __uint8_t namelen;    /* length of name bytes */
  117.         __uint8_t name[1];    /* name bytes */
  118.     } valuelist;            /* grows from bottom of buf */
  119. } xfs_attr_leafblock_t;
  120. typedef struct xfs_attr_leaf_hdr xfs_attr_leaf_hdr_t;
  121. typedef struct xfs_attr_leaf_map xfs_attr_leaf_map_t;
  122. typedef struct xfs_attr_leaf_entry xfs_attr_leaf_entry_t;
  123. typedef struct xfs_attr_leaf_name_local xfs_attr_leaf_name_local_t;
  124. typedef struct xfs_attr_leaf_name_remote xfs_attr_leaf_name_remote_t;
  125.  
  126. /*
  127.  * Flags used in the leaf_entry[i].flags field.
  128.  * NOTE: the INCOMPLETE bit must not collide with the flags bits specified
  129.  * on the system call, they are "or"ed together for various operations.
  130.  */
  131. #define    XFS_ATTR_LOCAL_BIT    0    /* attr is stored locally */
  132. #define    XFS_ATTR_ROOT_BIT    1    /* limit access to trusted attrs */
  133. #define    XFS_ATTR_SECURE_BIT    2    /* limit access to secure attrs */
  134. #define    XFS_ATTR_INCOMPLETE_BIT    7    /* attr in middle of create/delete */
  135. #define XFS_ATTR_LOCAL        (1 << XFS_ATTR_LOCAL_BIT)
  136. #define XFS_ATTR_ROOT        (1 << XFS_ATTR_ROOT_BIT)
  137. #define XFS_ATTR_SECURE        (1 << XFS_ATTR_SECURE_BIT)
  138. #define XFS_ATTR_INCOMPLETE    (1 << XFS_ATTR_INCOMPLETE_BIT)
  139.  
  140. /*
  141.  * Alignment for namelist and valuelist entries (since they are mixed
  142.  * there can be only one alignment value)
  143.  */
  144. #define    XFS_ATTR_LEAF_NAME_ALIGN    ((uint)sizeof(xfs_dablk_t))
  145.  
  146. /*
  147.  * Cast typed pointers for "local" and "remote" name/value structs.
  148.  */
  149. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME_REMOTE)
  150. xfs_attr_leaf_name_remote_t *
  151. xfs_attr_leaf_name_remote(xfs_attr_leafblock_t *leafp, int idx);
  152. #define XFS_ATTR_LEAF_NAME_REMOTE(leafp,idx)    \
  153.     xfs_attr_leaf_name_remote(leafp,idx)
  154. #else
  155. #define XFS_ATTR_LEAF_NAME_REMOTE(leafp,idx)    /* remote name struct ptr */ \
  156.     ((xfs_attr_leaf_name_remote_t *)        \
  157.      &((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ])
  158. #endif
  159. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME_LOCAL)
  160. xfs_attr_leaf_name_local_t *
  161. xfs_attr_leaf_name_local(xfs_attr_leafblock_t *leafp, int idx);
  162. #define XFS_ATTR_LEAF_NAME_LOCAL(leafp,idx)    \
  163.     xfs_attr_leaf_name_local(leafp,idx)
  164. #else
  165. #define XFS_ATTR_LEAF_NAME_LOCAL(leafp,idx)    /* local name struct ptr */ \
  166.     ((xfs_attr_leaf_name_local_t *)        \
  167.      &((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ])
  168. #endif
  169. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME)
  170. char *xfs_attr_leaf_name(xfs_attr_leafblock_t *leafp, int idx);
  171. #define XFS_ATTR_LEAF_NAME(leafp,idx)        xfs_attr_leaf_name(leafp,idx)
  172. #else
  173. #define XFS_ATTR_LEAF_NAME(leafp,idx)        /* generic name struct ptr */ \
  174.     (&((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ])
  175. #endif
  176.  
  177. /*
  178.  * Calculate total bytes used (including trailing pad for alignment) for
  179.  * a "local" name/value structure, a "remote" name/value structure, and
  180.  * a pointer which might be either.
  181.  */
  182. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_REMOTE)
  183. int xfs_attr_leaf_entsize_remote(int nlen);
  184. #define XFS_ATTR_LEAF_ENTSIZE_REMOTE(nlen)    \
  185.     xfs_attr_leaf_entsize_remote(nlen)
  186. #else
  187. #define XFS_ATTR_LEAF_ENTSIZE_REMOTE(nlen)    /* space for remote struct */ \
  188.     (((uint)sizeof(xfs_attr_leaf_name_remote_t) - 1 + (nlen) + \
  189.       XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1))
  190. #endif
  191. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_LOCAL)
  192. int xfs_attr_leaf_entsize_local(int nlen, int vlen);
  193. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL(nlen,vlen)    \
  194.     xfs_attr_leaf_entsize_local(nlen,vlen)
  195. #else
  196. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL(nlen,vlen)    /* space for local struct */ \
  197.     (((uint)sizeof(xfs_attr_leaf_name_local_t) - 1 + (nlen) + (vlen) + \
  198.       XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1))
  199. #endif
  200. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX)
  201. int xfs_attr_leaf_entsize_local_max(int bsize);
  202. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(bsize)    \
  203.     xfs_attr_leaf_entsize_local_max(bsize)
  204. #else
  205. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(bsize)    /* max local struct size */ \
  206.     (((bsize) >> 1) + ((bsize) >> 2))
  207. #endif
  208.  
  209.  
  210. /*========================================================================
  211.  * Structure used to pass context around among the routines.
  212.  *========================================================================*/
  213.  
  214. typedef struct xfs_attr_list_context {
  215.     struct xfs_inode        *dp;    /* inode */
  216.     struct attrlist_cursor_kern    *cursor;/* position in list */
  217.     struct attrlist            *alist;    /* output buffer */
  218.     int                count;    /* num used entries */
  219.     int                dupcnt;    /* count dup hashvals seen */
  220.     int                bufsize;/* total buffer size */
  221.     int                firstu;    /* first used byte in buffer */
  222.     int                flags;    /* from VOP call */
  223.     int                resynch;/* T/F: resynch with cursor */
  224. } xfs_attr_list_context_t;
  225.  
  226. /*
  227.  * Used to keep a list of "remote value" extents when unlinking an inode.
  228.  */
  229. typedef struct xfs_attr_inactive_list {
  230.     xfs_dablk_t    valueblk;    /* block number of value bytes */
  231.     int        valuelen;    /* number of bytes in value */
  232. } xfs_attr_inactive_list_t;
  233.  
  234.  
  235. /*========================================================================
  236.  * Function prototypes for the kernel.
  237.  *========================================================================*/
  238.  
  239. /*
  240.  * Internal routines when dirsize < XFS_LITINO(mp).
  241.  */
  242. int    xfs_attr_shortform_create(struct xfs_da_args *args);
  243. int    xfs_attr_shortform_add(struct xfs_da_args *add);
  244. int    xfs_attr_shortform_lookup(struct xfs_da_args *args);
  245. int    xfs_attr_shortform_getvalue(struct xfs_da_args *args);
  246. int    xfs_attr_shortform_to_leaf(struct xfs_da_args *args);
  247. int    xfs_attr_shortform_remove(struct xfs_da_args *remove);
  248. int    xfs_attr_shortform_list(struct xfs_attr_list_context *context);
  249. int    xfs_attr_shortform_replace(struct xfs_da_args *args);
  250. int    xfs_attr_shortform_allfit(struct xfs_dabuf *bp, struct xfs_inode *dp);
  251.  
  252. /*
  253.  * Internal routines when dirsize == XFS_LBSIZE(mp).
  254.  */
  255. int    xfs_attr_leaf_to_node(struct xfs_da_args *args);
  256. int    xfs_attr_leaf_to_shortform(struct xfs_dabuf *bp,
  257.                       struct xfs_da_args *args);
  258. int    xfs_attr_leaf_clearflag(struct xfs_da_args *args);
  259. int    xfs_attr_leaf_setflag(struct xfs_da_args *args);
  260. int    xfs_attr_leaf_flipflags(xfs_da_args_t *args);
  261.  
  262. /*
  263.  * Routines used for growing the Btree.
  264.  */
  265. int    xfs_attr_leaf_create(struct xfs_da_args *args, xfs_dablk_t which_block,
  266.                     struct xfs_dabuf **bpp);
  267. int    xfs_attr_leaf_split(struct xfs_da_state *state,
  268.                    struct xfs_da_state_blk *oldblk,
  269.                    struct xfs_da_state_blk *newblk);
  270. int    xfs_attr_leaf_lookup_int(struct xfs_dabuf *leaf,
  271.                     struct xfs_da_args *args);
  272. int    xfs_attr_leaf_getvalue(struct xfs_dabuf *bp, struct xfs_da_args *args);
  273. int    xfs_attr_leaf_add(struct xfs_dabuf *leaf_buffer,
  274.                  struct xfs_da_args *args);
  275. int    xfs_attr_leaf_remove(struct xfs_dabuf *leaf_buffer,
  276.                     struct xfs_da_args *args);
  277. int    xfs_attr_leaf_list_int(struct xfs_dabuf *bp,
  278.                       struct xfs_attr_list_context *context);
  279.  
  280. /*
  281.  * Routines used for shrinking the Btree.
  282.  */
  283. int    xfs_attr_leaf_toosmall(struct xfs_da_state *state, int *retval);
  284. void    xfs_attr_leaf_unbalance(struct xfs_da_state *state,
  285.                        struct xfs_da_state_blk *drop_blk,
  286.                        struct xfs_da_state_blk *save_blk);
  287. int    xfs_attr_root_inactive(struct xfs_trans **trans, struct xfs_inode *dp);
  288. int    xfs_attr_node_inactive(struct xfs_trans **trans, struct xfs_inode *dp,
  289.                       struct xfs_dabuf *bp, int level);
  290. int    xfs_attr_leaf_inactive(struct xfs_trans **trans, struct xfs_inode *dp,
  291.                       struct xfs_dabuf *bp);
  292. int    xfs_attr_leaf_freextent(struct xfs_trans **trans, struct xfs_inode *dp,
  293.                        xfs_dablk_t blkno, int blkcnt);
  294.  
  295. /*
  296.  * Utility routines.
  297.  */
  298. xfs_dahash_t    xfs_attr_leaf_lasthash(struct xfs_dabuf *bp, int *count);
  299. int    xfs_attr_leaf_order(struct xfs_dabuf *leaf1_bp,
  300.                    struct xfs_dabuf *leaf2_bp);
  301. int    xfs_attr_leaf_newentsize(struct xfs_da_args *args, int blocksize,
  302.                     int *local);
  303. int    xfs_attr_leaf_entsize(struct xfs_attr_leafblock *leaf, int index);
  304. int    xfs_attr_put_listent(struct xfs_attr_list_context *context,
  305.                  struct attrnames *, char *name, int namelen,
  306.                  int valuelen);
  307. int    xfs_attr_rolltrans(struct xfs_trans **transp, struct xfs_inode *dp);
  308.  
  309. #endif    /* __XFS_ATTR_LEAF_H__ */
  310.